package Hash$Set;

import common.DoubleListNode;

import java.util.HashMap;
import java.util.Map;

/**
 * LRU 缓存设计
 * https://leetcode-cn.com/problems/lru-cache/
 * LRU 缓存基本思想：当空间内容不足时，优先删除最长时间没有被使用的元素，
 * 相当于一个队列（最先进队列且没有被使用的元素，优先出队列）。
 * 缓存支持获取元素和写入元素两个操作
 * 在获取元素的时候，首先要判断该元素在不在缓存中，然后使用该元素（即需要该元素重新进入缓存）
 * 写入元素，判断是否超出缓存最大值，还有空间直接写入，超出最大值，则先删除再写入
 * 提交失败记录点：当key已经存在时，更新value，并且执行被使用的记录
 */
public class LRUCache {
    DoubleListNode head = new DoubleListNode(); // 保护头结点
    DoubleListNode tail = new DoubleListNode(); // 保护尾结点
    int capacity = 0; // 记录最大容量
    Map<Integer, DoubleListNode> keyMark = new HashMap<>(); // key是否存在以及位置的标记

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.pre = null;
        head.next = tail;
        tail.pre = head;
        tail.next = null;
    }

    public int get(int key) {
        if (keyMark.containsKey(key)){
            DoubleListNode node = keyMark.get(key);
            updateNode(node, key); // 新插入该 node
            return node.value;
        }
        return -1;
    }

    /**
     * 当 key 被使用时，更新node位置到最头部
     * @param node
     */
    public void updateNode(DoubleListNode node, int key){
        remove(node, key); // 删掉原来位置的 node
        DoubleListNode nextNode = head.next;
        node.next = head.next;
        node.pre = head;
        head.next = node;
        nextNode.pre = node;
        keyMark.put(key, node);
    }

    /**
     * 插入新的元素，在插入前先判断空间是否可用
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        // 如果key已经存在，变更值，并且更新位置
        if (keyMark.containsKey(key)){
            DoubleListNode node = keyMark.get(key);
            node.value = value;
            updateNode(node, key);
            return;
        }
        // 如果空间不可用，先删除尾部元素
        if (keyMark.size() >= capacity){
            DoubleListNode lastNode = tail.pre;
            remove(lastNode, lastNode.key);
        }
        DoubleListNode newNode = new DoubleListNode(key, value, head.next, head);
        DoubleListNode nextNode = head.next;
        head.next = newNode;
        nextNode.pre = newNode;
        keyMark.put(key, newNode); // 维护key是否存在标识
    }

    /**
     * 删除操作：删除缓存中对应的结点，并且将标记位同时删除
     * @param node 要删除的结点
     * @param k 标记位
     */
    private void remove(DoubleListNode node, int k){
        node.pre.next = node.next;
        node.next.pre = node.pre;
        keyMark.remove(k);
    }
}
